allocator原理介绍

考虑到小型区域可能造成内存破碎问题，SGI STL设计了双层级配置器，第一层配置器直接使用malloc()和free()，第二层配置器则视情况采用不同的策略：当配置区块超过128bytes时，调用第一层级配置器，当配置区块小于128bytes时，采用复杂的memory pool方式。

第一级配置器__malloc_alloc_template

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//以下是第第一级配置器
template <int inst>
class __malloc_alloc_template {
private:
//以下函数用来处理内存不足的情况
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
static void (* __malloc_alloc_oom_handler)();
public:
static void * allocate(size_t n)
{
    void *result = malloc(n);                    //第一级配置器，直接使用malloc()
    //如果内存不足，则调用内存不足处理函数oom_alloc()来申请内存
    if (0 == result) result = oom_malloc(n);
    return result;
}
static void deallocate(void *p, size_t /* n */)
{
    free(p);            //第一级配置器直接使用 free()
}
static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
    void * result = realloc(p, new_sz);            //第一级配置器直接使用realloc()
    //当内存不足时，则调用内存不足处理函数oom_realloc()来申请内存
    if (0 == result) result = oom_realloc(p, new_sz);
    return result;
}
//设置自定义的out-of-memory handle就像set_new_handle()函数
static void (* set_malloc_handler(void (*f)()))()
{
    void (* old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = f;
    return(old);
}
};
template <int inst>　　　　
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;　　//内存处理函数指针为空，等待客户端赋值
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
    void (* my_malloc_handler)();
    void *result;
    for (;;) {                                                     //死循环
        my_malloc_handler = __malloc_alloc_oom_handler;            //设定自己的oom(out of memory)处理函数
        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }         //如果没有设定自己的oom处理函数，毫不客气的抛出异常
        (*my_malloc_handler)();                                    //设定了就调用oom处理函数
        result = malloc(n);                                        //再次尝试申请
        if (result) return(result);
    }
}
template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)
{
    void (* my_malloc_handler)();
    void *result;
    for (;;) {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }    //如果自己没有定义oom处理函数，则编译器毫不客气的抛出异常
        (*my_malloc_handler)();                                //执行自定义的oom处理函数
        result = realloc(p, n);                                //重新分配空间
        if (result) return(result);                            //如果分配到了，返回指向内存的指针
    }
}

上面代码看起来复杂，其实流程是这样的：

  • 通过allocate()申请内存，通过deallocate()来释放内存，通过reallocate()重新分配内存
  • 当allocate()或reallocate()分配内存不足时会调用oom_malloc()或oom_remalloc()来处理
  • 当oom_malloc() 或 oom_remalloc()还是没能分配到申请的内存时，会转如下两步中的一步：
    • 调用用户自定义的内存分配不足处理函数(这个函数通过set_malloc_handler() 来设定)，然后继续申请内存
    • 如果用户未定义内存分配不足处理函数，程序就会抛出bad_alloc异常或利用exit(1)终止程序

第二级配置器__default_alloc_template

当申请的内存大于 128 bytes时就调用第一层配置器。当申请的内存小于 128bytes时才会调用第二层配置器。第二层配置器如何维护128bytes以下内存的配置呢？ SGI 第二层配置器定义了一个 free-lists，这个free-list是一个数组，如下图：

这个数组的元素都是指针，用来指向16个链表的表头，这16个链表上面挂的都是可以用的内存块。只是不同链表中元素的内存块大小不一样，16个链表上分别挂着大小为8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128 bytes的小额区块，图如下：

下面我们看下allocate()代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static void * allocate(size_t n)
{
    obj * __VOLATILE * my_free_list;
    obj * __RESTRICT result;
    //要申请的空间大于128bytes就调用第一级配置
    if (n > (size_t) __MAX_BYTES) {
      	return(malloc_alloc::allocate(n));
    }
    //寻找 16 个free lists中恰当的一个
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if (result == 0) {
        //没找到可用的free list，准备新填充free list
        void *r = refill(ROUND_UP(n));
        return r;
    }
    *my_free_list = result -> free_list_link;
    return (result);
};

其中有两个函数我来提一下，一个是ROUND_UP()，这个是将要申请的内存字节数上调为8的倍数。因为我们free-lists中挂的内存块大小都是8的倍数嘛，这样才知道应该去找哪一个链表。另一个就是refill()。这个是在没找到可用的free list的时候调用，准备填充free lists。意思是：参考上图，假设我现在要申请大小为 56bytes 的内存空间，那么就会到free lists 的第 7 个元素所指的链表上去找。如果此时 #7元素所指的链表为空怎么办？这个时候就要调用refill()函数向内存池申请N（一般为20个）个大小为56bytes的内存区块，然后挂到 #7 所指的链表上。这样，申请者就可以得到内存块了。当然，这里为了避免复杂，误导读者我就不讨论refill()函数了。allocate()过程图如下：

下面再看下deallocate()的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void deallocate(void *p, size_t n)
{
    obj *q = (obj *)p;
    obj * __VOLATILE * my_free_list;
    //如果要释放的字节数大于128，则调第一级配置器
    if (n > (size_t) __MAX_BYTES) {
        malloc_alloc::deallocate(p, n);
        return;
    }
    //寻找对应的位置
    my_free_list = free_list + FREELIST_INDEX(n);
    //以下两步将待释放的块加到链表上
    q -> free_list_link = *my_free_list;    
    *my_free_list = q;
}

说明

本文转载自文章浅析STL allocator。